◀ Prev · Parts · Full · Next ▶

For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a ρ-approximation algorithm A is defined to be an algorithm for which it has been proven that the value/cost, f(x), of the approximate solution A(x) to an instance x will not be more (or less, depending on the situation) than a factor ρ times the value, OPT, of an optimum solution.

{ O P T ≤ ≤ f ( x ) ≤ ≤ ρ ρ O P T , if ρ ρ > 1 ; ρ ρ O P T ≤ ≤ f ( x ) ≤ ≤ O P T , if ρ ρ < 1. {\displaystyle {\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{cases}}}

The factor ρ is called the relative performance guarantee. An approximation algorithm has an absolute performance guarantee or bounded error c, if it has been proven for every instance x that

( O P T − − c ) ≤ ≤ f ( x ) ≤ ≤ ( O P T + c ) . {\displaystyle (\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c).}

Similarly, the performance guarantee, R(x,y), of a solution y to an instance x is defined as

R ( x , y ) = max ( O P T f ( y ) , f ( y ) O P T ) , {\displaystyle R(x,y)=\max \left({\frac {OPT}{f(y)}},{\frac {f(y)}{OPT}}\right),}

◀ Prev · Parts · Full · Next ▶